package leetcode_600;

/**
 *@author 周杨
 *BeautifulArrangement_526 一个美丽的排列定义为 第i上的元素可以整除i或者被i整除 问这样的排列数的数量
 *describe:用回溯 visited数组监控遍历与否 AC 20%
 *2018年9月11日 上午10:02:28
 */
public class BeautifulArrangement_526 {
	 int res=0;
	 boolean visited[];
	 int N;
	 public int countArrangement(int N) {
		 this.visited=new boolean[N+1];
		 this.N=N;
	     help(1);   
		 return this.res;
	 }
	 
	 private void help(int index) {
		 if(index==this.N+1) {
			 ++this.res;
			 return ;
		 }
		 for(int i=1;i<=N;++i) {
			 if(!this.visited[i]) {
				 if(i%index==0||index%i==0) {
					 this.visited[i]=true;
					 help(index+1);
					 this.visited[i]=false;
				 }	 
			 }
		 }
	 }
}
